36. 贪心歌手

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let lines = [];
rl.on('line', (line) => {
    lines.push(line);
});
rl.on('line', () => {
    const [T, N] = lines[0].split(' ').map(Number);
    const travelDays = lines[1].split(' ').map(Number);
    const M = [];
    const D = [];
    for(let i=2; i<2+N; i++) {
        const [m,d] = lines[i].split(' ').map(Number);
        M.push(m);
        D.push(d);
    }
    const roadCost = travelDays.reduce((acc, val) => acc+val, 0);
    const remain = T - roadCost;
    let earnings = [];
    for(let i=0; i<N; i++) {
        let days = 0;
        while(true) {
            const today = Math.max(M[i]-days*D[i], 0);
            if (earnings.length < remain) {
                earnings.push(today);
            } else {
                const minIndex = earnings.indexOf(Math.min(...earnings));
                if (earnings[minIndex] < today) {
                    earnings[minIndex] = today;
                }
            }
            if(today === 0) {
                break;
            }
            days++;
        }
    }
    const maxEarnings = earnings.reduce((acc,val)=>acc+val, 0);
    console.log(maxEarnings);
})